package list;

class ListNode {
	int val;
	ListNode next;

	ListNode() {
	}

	ListNode(int val) {
		this.val = val;
	}

	ListNode(int val, ListNode next) {
		this.val = val;
		this.next = next;
	}
}

//提交代码， 将类名ReverseGroup -> Solution
public class ReverseGroup {
	// 题目给定k最大5000，那么5001肯定足够了。 实测1201也可以
	public static int MAX = 5001;
	// 类静态数组充当栈
	public static ListNode[] stack = new ListNode[MAX];
	// 记录栈的大小， size == 0意味栈空。
	public static int size;

	// 主方法
	public ListNode reverseKGroup(ListNode head, int k) {
		if (k < 2) {
			return head;
		}
		size = 0;
		return f(head, k);
	}

	/**
	 * 
	 * @param head 原链表头节点
	 * @param k    每k个逆序
	 * @return 返回新链表的头节点
	 */
	private ListNode f(ListNode head, int k) {
		ListNode newHead = head, cur = head;
		ListNode prev = null, next = null;
		while (cur != null) {
			next = cur.next;
			stack[size++] = cur;
			if (size == k) {
				prev = reversePart(prev, next);
				newHead = newHead == head ? cur : newHead;
			}
			cur = next;
		}
		return newHead;
	}

	/**
	 * 
	 * @param left  修改局部链表头节点的前驱
	 * @param right 修改局部链表尾节点的后继
	 * @return 返回下一对修改局部链表的前驱节点。
	 */
	private ListNode reversePart(ListNode left, ListNode right) {
		ListNode cur = stack[--size];
		if (left != null) {
			left.next = cur;
		}
		ListNode next = null;
		while (size > 0) {
			next = stack[--size];
			cur.next = next;
			cur = next;
		}
		cur.next = right;
		return cur;
	}
	//提交时，注意修改函数名
	public ListNode reverseKGroup1(ListNode head, int k) {
		// 特殊输入判断
		if (k < 2) {
			return head;
		}
		ListNode cur = head, start = null, prev = null, next = null;
		int count = 1;// 计数变量。
		while (cur != null) {
			next = cur.next;// 后继始终跟着循环更新。
			if (count == k) {
				start = prev == null ? head : prev.next;// 获得当前逆序对开始节点
				head = prev == null ? cur : head;// 第一组逆序需要修改头节点
				reversePart2(prev, start, cur, next);// (prev,next),[start,end]
				prev = start;// 更新前驱范围
				count = 0;// 重置
			}
			++count;// 自增
			cur = next;// cur跟着next。
		}
		return head;// head指向的更新后的头节点或者原先的头节点。
	}

	private void reversePart2(ListNode left, ListNode start, ListNode end,ListNode right) {
		//反转部分链表一样的逻辑 
		ListNode prev = start,next = null, cur = start.next;
		 while(cur != right){
			 next = cur.next;
			 cur.next = prev;
			 prev = cur;
			 cur = next;
		 }
		 if(left!=null) {
			 left.next = end;
		 }
		 start.next = right;
	}
}